package com.zs.letcode.top_interview_questions;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 有效的字母异位词
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * <p>
 * 示例1:
 * <p>
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: s = "rat", t = "car"
 * 输出: false
 * 说明:
 * 你可以假设字符串只包含小写字母。
 * <p>
 * 进阶:
 * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 * <p>
 * 相关标签
 * 排序
 * 哈希表
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xar9lv/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * <p>
 * <p>
 *
 * @author madison
 * @description
 * @date 2021/5/27 07:36
 */
public class Chapter12 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：排序
         * t 是 ss 的异位词等价于「两个字符串排序后相等」
         */
        public boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) {
                return false;
            }
            char[] str1 = s.toCharArray();
            char[] str2 = s.toCharArray();
            Arrays.sort(str1);
            Arrays.sort(str2);

            return Arrays.equals(str1, str2);
        }

        /**
         * 方法二：哈希表
         * tt 是 ss 的异位词等价于「两个字符串中字符出现的种类和次数均相等」
         */
        public boolean isAnagram1(String s, String t) {
            if (s.length() != t.length()) {
                return false;
            }
            int[] table = new int[26];
            for (int i = 0; i < s.length(); i++) {
                table[s.charAt(i) - 'a']++;
            }
            for (int i = 0; i < t.length(); i++) {
                table[t.charAt(i) - 'a']--;
                if (table[t.charAt(i) - 'a'] < 0) {
                    return false;
                }
            }
            return true;
        }

        /**
         * 进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。
         * 同时读者需要注意Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。
         */
        public boolean isAnagram2(String s, String t) {
            if (s.length() != t.length()) {
                return false;
            }
            Map<Character, Integer> table = new HashMap();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                table.put(ch, table.getOrDefault(ch, 0) + 1);
            }
            for (int i = 0; i < t.length(); i++) {
                char ch = t.charAt(i);
                table.put(ch, table.getOrDefault(ch, 0) - 1);
                if (table.get(ch) < 0) {
                    return false;
                }
            }
            return true;
        }
    }
}
